

inline size_t Parent(size_t x)
{
	return x/2;
}

inline size_t Left(size_t x)
{
	return 2*x;
}

inline size_t Right(size_t x)
{
	return 2*x+1;
}

template<typename T>
void MaxHeapify(T *vec, size_t cnt, size_t pos)
{
	size_t l=Left(pos);
	size_t r=Right(pos);
	size_t largest=pos;
	if(l<cnt && vec[l]>vec[largest])
		largest=l;
	if(r<cnt && vec[r]>vec[largest])
		largest=r;
	if(largest != pos)
	{
		T temp=vec[pos];
		vec[pos]=vec[largest];
		vec[largest]=temp;
		MaxHeapify(vec,cnt,largest);
	}
}

template<typename T>
void BuildMaxHeap(T *vec, size_t cnt)
{
	size_t endPos=cnt/2;
	for(size_t i = 0 ;i <=endPos; ++i)
	{
		MaxHeapify(vec,cnt,i);
	}
}

template<typename T>
void HeapSort(T *vec, size_t cnt)
{
	BuildMaxHeap(vec,cnt);
	for(size_t i = cnt; i>=2;)
	{
		T temp=vec[i-1];
		vec[i-1]=vec[0];
		vec[0]=temp;
		MaxHeapify(vec,--i,0);
	}
}